import java.util.Arrays;

public class Code03_CountingSort {
    // 计数排序方法，接受一个整数数组作为参数，返回排序后的数组
    public static int[] countingSort(int[] arr) {
        // 如果输入数组为null或者长度小于等于1，直接返回原数组
        // 因为空数组或只有一个元素的数组本身就是有序的
        if (arr == null || arr.length <= 1) {
            return arr;
        }

        // 找出数组中的最大值和最小值，用于确定计数数组的范围
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            // 如果当前数字大于最大值，则更新最大值
            if (num > max) {
                max = num;
            }
            // 如果当前数字小于最小值，则更新最小值
            else if (num < min) {
                min = num;
            }
        }

        // 创建计数数组，其长度为最大值与最小值的差加1
        // 这样计数数组的每个索引就可以对应于原数组中的一个值（经过最小值偏移）
        int[] count = new int[max - min + 1];
        // 统计原数组中每个值出现的次数
        // 通过将每个数减去最小值来得到在计数数组中的偏移索引
        for (int num : arr) {
            count[num - min]++;
        }

        // 将计数数组转换为每个元素的最终位置索引数组
        // 这里的操作是对计数数组进行累加
        // 例如，如果count[0]=3，count[1]=2，那么经过这个循环后count[1]=5
        // 表示原数组中值为1（假设最小值为0）的最后一个元素应该放在新数组的第5个位置（索引为4）
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 创建一个与原数组长度相同的输出数组，用于存储排序后的结果
        int[] output = new int[arr.length];
        // 从原数组的末尾开始遍历
        for (int i = arr.length - 1; i >= 0; i--) {
            // 根据计数数组中的位置信息，将原数组中的元素放入输出数组中正确的位置
            // 注意这里要先减1，因为数组索引从0开始
            output[count[arr[i] - min] - 1] = arr[i];
            // 将计数数组中对应位置的值减1，表示已经处理了一个该值的元素
            count[arr[i] - min]--;
        }

        // 返回排序后的数组
        return output;
    }

    // 主方法，用于测试计数排序算法
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        // 调用计数排序方法对数组进行排序
        int[] sorted = countingSort(arr);
        // 输出排序后的数组
        System.out.println(Arrays.toString(sorted));
    }
}